package com.gorkr.backtracking;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author gorkr
 * @date 2022/09/14 14:31
 **/
public class M78SubSets {
    private List<List<Integer>> res = new LinkedList<>();
    private boolean[] visited;

    public List<List<Integer>> subsets(int[] nums) {

        Arrays.sort(nums);


        visited = new boolean[nums.length];
        backTracking(nums, new LinkedList<>());
        res.add(new ArrayList<>());

        return res;
    }

    private void backTracking(int[] nums, LinkedList<Integer> trace) {
        // basecase
        if (trace.size()>=nums.length){
            return;
        }

        // 做选择
        for (int i = 0; i < nums.length; i++) {
            if(visited[i]||(!trace.isEmpty() && nums[i]<=trace.getLast())){
                continue;
            }
            visited[i] = true;
            trace.add(nums[i]);
            res.add(new ArrayList<>(trace));

            backTracking(nums, trace);

            // 撤销
            visited[i] = false;
            trace.removeLast();
        }
    }

    @Test
    public void test(){
        System.out.println(subsets(new int[]{0}).toString());

    }


}
    